home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / man / prog / graph.prog < prev    next >
Encoding:
Text File  |  1994-08-05  |  11.4 KB  |  396 lines
  1. {\bf Depth First Search}
  2.  
  3. \#include \<LEDA/graph.h\>\nl
  4. \#include \<LEDA/stack.h\>
  5. \medskip
  6. \cleartabs
  7. \+list\<node\> DFS($graph\& G,\  node\  v,\  node\_array\<bool\>\& reached$)\cr
  8. \+$\{$\ \ &\cr 
  9. \+  &list\<node\>  $L$;\cr
  10. \+  &stack\<node\> $S$;\cr
  11. \+  &node $w$;\cr
  12. \smallskip
  13. \+  &\If ( ! $reached[v]$ )\cr
  14. \+  &\ \ \ &$\{$ &$reached[v]$ = true;\cr
  15. \+  &      &     &$L$.append($v$);\cr
  16. \+  &      &     &$S$.push($v$);\cr
  17. \+  &      &\ $\}$\cr
  18. \smallskip
  19. \+  &{\bf while} ( !$S$.empty() )\cr
  20. \+  &      &$\{$ &$v = S$.pop(); \cr
  21. \+  &      &     &{\bf forall\_adj\_nodes}($w,v$) \cr
  22. \+  &      &     &\ \ \ &{\bf if} ( !$reached[w]$ ) \cr
  23. \+  &      &     &      &$\{$ &$reached[w]$ = true;\cr
  24. \+  &      &     &      &     &$L$.append($w$);\cr
  25. \+  &      &     &      &     &$S$.push($w$);\cr
  26. \+  &      &     &      &\ $\}$\cr
  27. \+  &      &\ $\}$\cr
  28. \smallskip
  29. \+  &return $L$;\cr
  30. \+$\}$\cr
  31.  
  32. \vfill\eject
  33.  
  34. {\bf Breadth First Search}
  35.  
  36. \#include \<LEDA/graph.h\>\nl
  37. \#include \<LEDA/queue.h\>
  38. \medskip
  39. \cleartabs
  40. \+void BFS($graph\&\ G,\ node\ v,\ node\_array\<int\>\&\ dist$)\cr
  41. \+$\{$\ \ &\cr
  42. \+  &queue\<node\> $Q$;\cr
  43. \+  &node $w$;\cr
  44. \smallskip
  45. \+  &{\bf forall\_nodes}($w,G$) $dist[w] = -1$;\cr
  46. \smallskip
  47. \+  &$dist[v] = 0$;\cr
  48. \+  &$Q$.append($v$);\cr
  49. \smallskip
  50. \+  &{\bf while} ( !$Q$.empty() )\cr
  51. \+  &\ \ &$\{$ &$v = Q$.pop();\cr
  52. \+  &    &     &{\bf forall\_adj\_nodes}($w,v$)\cr
  53. \+  &    &     &\ \ \ &{\bf if} ($dist[w] < 0$) \cr
  54. \+  &    &     &      &$\{$ &$Q$.append($w$); \cr
  55. \+  &    &     &      &     &$dist[w] = dist[v]+1$;\cr
  56. \+  &    &     &      &\ $\}$\cr
  57. \+  &    &\ $\}$\cr
  58. \smallskip
  59. \+$\}$\cr
  60.  
  61. {\bf Connected Components}
  62.  
  63. \#include \<LEDA/graph.h\>
  64. \medskip
  65. \cleartabs
  66. \+int COMPONENTS($ugraph\&\ G,\ node\_array\<int\>\&\ compnum$)\cr
  67. \+$\{$ \ & \cr
  68. \+  &node $v,w$;\cr
  69. \+  &list\<node\> $S$;\cr
  70. \+  &int $count = 0$;\cr
  71. \smallskip
  72. \+  &node\_array(bool) $reached(G,false)$;\cr
  73. \smallskip
  74. \+  &\Forallnodes($v,G$) \cr
  75. \+  &\ \ \ &\If ( !$reached[v]$ ) \cr
  76. \+  &      &\ \ &$\{$ &$S$ = DFS($G,v,reached$);\cr
  77. \+  &      &    &     &\Forall($w,S$) $compnum[w] = count$;\cr
  78. \+  &      &    &     &$count++$; \cr
  79. \+  &      &    &\ $\}$\cr
  80. \smallskip
  81. \+  &\Return $count$;\cr
  82. \+\ $\}$\cr
  83.  
  84. \vfill\eject
  85.  
  86.  
  87.  
  88. {\bf Depth First Search Numbering}
  89.  
  90. \#include \<LEDA/graph.h\>
  91. \medskip
  92. \cleartabs
  93. \+int $dfs\_count1,\ dfs\_count2$;\cr
  94. \medskip
  95. \+void d\_f\_s($node\ v,\ node\_array\<bool\>\&\ S$,
  96.                                         &$node\_array\<int\>\&\ dfsnum$, \cr
  97. \+                                      &$node\_array\<int\>\&\ compnum$,\cr
  98. \+                                      &$list\<edge\>\ T$ )\cr
  99. \cleartabs
  100. \+$\{$ \ &// recursive DFS\cr
  101. \smallskip
  102. \+  &node $w$;\cr
  103. \+  &edge $e$;\cr
  104. \smallskip
  105. \+  &$S[v] = true$;\cr
  106. \+  &$dfsnum[v] = ++dfs\_count1$;\cr
  107. \smallskip
  108. \+  &\Foralladjedges($e,v$) \cr
  109. \+  &\ \ \ &$\{$ &$w = G$.target(e);\cr
  110. \+  &      &    &\If ( !$S[w]$ ) \cr
  111. \+  &      &    &\ \ &$\{$ &$T$.append($e$);\cr
  112. \+  &      &    &    &    &d\_f\_s($w,S,dfsnum,compnum,T$);\cr
  113. \+  &      &    &    &\ $\}$\cr
  114. \+  &      &\ $\}$\cr
  115. \smallskip
  116. \+  &$compnum[v] = ++dfs\_count2$;\cr
  117. \+\ $\}$ \cr
  118. \bigskip
  119. \bigskip
  120. \cleartabs
  121. \+list\<edge\> DFS\_NUM($graph\&\ G,\ node\_array\<int\>\&\ dfsnum,\ node\_array\<int\>\&\ compnum$ )\cr
  122. \+$\{$ \ & \cr
  123. \+  &list\<edge\> $T$;\cr
  124. \+  &node\_array\<bool\> $reached(G,false)$;\cr
  125. \+  &node $v$;\cr
  126. \+  &$dfs\_count1 = dfs\_count2 = 0$;\cr
  127. \+  &\Forallnodes($v,G$) \cr
  128. \+  & \ \ \ \If ( !$reached[v]$ ) d\_f\_s($v,reached,dfsnum,compnum,T$);\cr
  129. \+  &\Return $T$;\cr
  130. \+\ $\}$\cr
  131.  
  132. \vfill\eject
  133.  
  134.  
  135.  
  136. {\bf Topological Sorting}
  137.  
  138. \#include \<LEDA/graph.h\>
  139. \medskip
  140. \cleartabs
  141. \+bool TOPSORT($graph\&\ G,\ node\_array\<int\>\& ord$)\cr
  142. \+$\{$\ \ &\cr 
  143. \+  &node\_array\<int\> INDEG($G$);\cr
  144. \+  &list\<node\> ZEROINDEG;\cr
  145. \smallskip
  146. \+  &int $count=0$;\cr
  147. \+  &node $v,w$;\cr
  148. \+  &edge $e$;\cr
  149. \smallskip
  150. \+  &{\bf forall\_nodes}($v,G$)\cr
  151. \+  &\ \ \ {\bf if} ((INDEG[$v$]=$G$.indeg($v$))==0) ZEROINDEG.append($v$); \cr
  152. \smallskip
  153. \+  &{\bf while} (!ZEROINDEG.empty())\cr
  154. \+  &\ \ &$\{$ &$v$ = ZEROINDEG.pop();\cr
  155. \+  &    &    &$ord[v] = ++count$;\cr
  156. \smallskip
  157. \+  &    &    &{\bf forall\_adj\_nodes}($w,v$) \cr
  158. \+  &    &    &\ \ \ {\bf if} ($--$INDEG[$w$]==0) ZEROINDEG.append($w$);\cr
  159. \+  &    &\ $\}$\cr
  160. \smallskip
  161. \+  &{\bf return} (count==G.number\_of\_nodes()); \cr
  162. \smallskip
  163. \+\ $\}$\cr
  164.  
  165. \bigskip
  166. //TOPSORT1 sorts node and edge lists according to the topological ordering:
  167. \bigskip
  168. \cleartabs
  169. \+$bool$ TOPSORT1($graph\&\ G$)\cr
  170. \+$\{$\ \ &node\_array\<int\> node\_ord($G$);\cr
  171. \+        &edge\_array\<int\> edge\_ord($G$);\cr
  172. \smallskip
  173. \+        &{\bf if} (TOPSORT(G,node\_ord))\cr
  174. \+        &$\{$\ &edge $e$;\cr
  175. \+        &      &{\bf forall\_edges}($e,G$) edge\_ord[$e$]=node\_ord[$target(e)$];\cr
  176. \+        &      &$G$.sort\_nodes(node\_ord);\cr
  177. \+        &      &$G$.sort\_edges(edge\_ord);\cr
  178. \+        &      &{\bf return} true;\cr
  179. \+        &$\ \}$\cr
  180. \+        &{\bf return} false;\cr
  181. \+$\ \}$\cr
  182.  
  183. \vfill\eject
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190. {\bf Strongly Connected Components}
  191.  
  192. \#include \<LEDA/graph.h\>\nl
  193. \#include \<LEDA/array.h\>
  194. \medskip
  195. \cleartabs
  196. \+int STRONG\_COMPONENTS($graph\&\ G,\ node\_array\<int\>\&\ compnum$)\cr
  197. \+$\{$ \ &\cr
  198. \+  &node $v,w$;\cr
  199. \+  &int $n = G$.number\_of\_nodes();\cr
  200. \+  &int $count = 0$;\cr
  201. \+  &int $i$;\cr
  202. \smallskip
  203. \+  &array\<node\> $V(1,n)$;\cr
  204. \+  &list\<node\> $S$;\cr
  205. \+  &node\_array\<int\>  $dfs\_num(G), compl\_num(G)$;\cr
  206. \+  &node\_array\<bool\> $reached(G,false)$;\cr
  207. \smallskip
  208. \+  &DFS\_NUM($G,dfs\_num,compl\_num$);\cr
  209. \smallskip
  210. \+  &\Forallnodes($v,G$) $V[compl\_num[v]] = v$;\cr
  211. \smallskip
  212. \+  &$G$.rev();\cr
  213. \smallskip
  214. \+  &\For($i=n;\ i>0;\ i--$)\cr
  215. \+  &\ \ \ &\If ( !$reached[V[i]]$ ) \cr
  216. \+  &      &\ \ &$\{$ &$S$ = DFS($G,V[i],reached$);\cr
  217. \+  &      &    &     &\Forall($w,S$) $compnum[w] = count$;\cr
  218. \+  &      &    &     &$count++$;\cr
  219. \+  &      &    &\ $\}$\cr
  220. \smallskip
  221. \+  &\Return $count$;\cr
  222. \smallskip
  223. \+\ $\}$\cr
  224.  
  225. \vfill\eject
  226.  
  227.  
  228.  
  229.  
  230.  
  231. {\bf Dijkstra's Algorithm}
  232.  
  233.  
  234. \#include \<LEDA/graph.h\>\nl 
  235. \#include \<LEDA/node\_pq.h\>
  236. \medskip
  237. \cleartabs
  238. \+void DIJKSTRA(& graph\& $G$, node $s$, edge\_array\<int\>\& $cost$, \cr
  239. \+              & node\_array\<int\>\& $dist$, node\_array\<edge\>\& $pred$ )\cr
  240. \+\cleartabs 
  241.   $\{$ & node\_pq\<int\> $PQ(G)$;\cr
  242. \smallskip
  243. \+     &int $c$;\cr
  244. \+     &node $u,v$;\cr
  245. \+     &edge $e$;\cr
  246. \smallskip
  247. \+     &{\bf forall\_nodes}($v,G$)\cr
  248. \+     &\ \ \ &$\{$ & $ pred[v] = 0$;\cr
  249. \+     &      &     & $dist[v] = infinity$;\cr
  250. \+     &      &     & $PQ$.insert($v,dist[v])$;\cr
  251. \+     &      &\ $\}$\cr
  252. \smallskip
  253. \+     &$dist[s] = 0$;\cr
  254. \+     &$PQ$.decrease\_inf($s,0)$;\cr
  255. \smallskip
  256. \+     &{\bf while} ( ! $PQ$.empty())\cr
  257. \+     &\ \ \ &$\{$ &$u = PQ$.del\_min()\cr
  258. \smallskip
  259. \+     &      &     &{\bf forall\_adj\_edges}($e,u$)\cr
  260. \+     &      &     &\ \ \ &$\{$ &$v = G.target(e) $;       \cr
  261. \+     &      &     &      &     &$c = dist[u] + cost[e] $;\cr
  262. \+     &      &     &      &     &{\bf if} ( $c < dist[v] $)\cr
  263. \+     &      &     &      &     &\ \ &$\{$ &$dist[v] = c$;\cr
  264. \+     &      &     &      &     &    &     &$pred[v] = e$;\cr
  265. \+     &      &     &      &     &    &     &$PQ$.decrease\_inf($v,c$);\cr
  266. \+     &      &     &      &     &    &\ $\}$\cr
  267. \+     &      &     &      &\ $\}$ /$*$ forall\_adj\_edges $*$/\cr
  268. \smallskip
  269. \+     &      &\ $\}$ /$*$ while $*$/\cr
  270. \smallskip
  271. \+$\}$\cr
  272.  
  273. \vfill\eject
  274.  
  275. {\bf Bellman/Ford Algorithm}
  276.  
  277. \#include \<LEDA/graph.h\>\nl
  278. \#include \<LEDA/queue.h\>
  279. \medskip
  280. \cleartabs
  281. \+bool BELLMAN\_FORD(&$graph\&\ G,\ node\ s,\ edge\_array\<int\>\&\ cost$,\cr
  282. \+                   &$node\_array\<int\>\&\ dist,\ node\_array\<edge\>\&\ pred$)\cr
  283. \+\cleartabs
  284.   $\{$ \ 
  285.     &node\_array\<bool\> $in\_Q(G,false)$;\cr
  286. \+  &node\_array\<int\>  $count(G,0)$;\cr
  287. \smallskip
  288. \+  &int $n = G$.number\_of\_nodes();\cr
  289. \+  &queue\<node\> $Q(n)$;\cr
  290. \smallskip
  291. \+  &node $u,v$;\cr
  292. \+  &edge $e$;\cr
  293. \+  &int  $c$;\cr
  294. \smallskip
  295. \+  &\Forallnodes($v,G$) \ &$\{$ &$pred[v] = 0$;\cr
  296. \+  &                      &     &$dist[v] =  infinity$; \cr
  297. \+  &                      &\ $\}$\cr
  298. \+  &\cleartabs
  299.      $dist[s] = 0$;\cr
  300. \+  &$Q$.append($s$);\cr
  301. \+  &$in\_Q[s] = true$;\cr
  302. \smallskip
  303. \+  &while (!$Q$.empty())\cr
  304. \+  &\ \ \ &$\{$ &$u = Q$.pop();\cr
  305. \+  &      &     &$in\_Q[u] = false$;\cr
  306. \smallskip
  307. \+  &      &     &\If ($++count[u] > n$)  {\bf return} false;\quad //negative cycle\cr
  308. \smallskip
  309. \+  &      &     &\Foralladjedges($e,u$) \cr
  310. \+  &      &     &\ \ \ &$\{$ &$v$ = $G$.target($e$);\cr
  311. \+  &      &     &      &$c = dist[u] + cost[e]$;\cr
  312. \smallskip
  313. \+  &      &     &      &\If ($c < dist[v]$) \cr
  314. \+  &      &     &      &\ \ &$\{$ &$dist[v] = c$; \cr
  315. \+  &      &     &      &    &     &$pred[v] = e$;\cr
  316. \+  &      &     &      &    &     &\If (!$in\_Q[v]$)  \cr
  317. \+  &      &     &      &    &     &\ \ &$\{$ &$Q$.append($v$);\cr
  318. \+  &      &     &      &    &     &    &     &$in\_Q[v]=true$;\cr
  319. \+  &      &     &      &    &     &    &\ $\}$\cr
  320. \+  &      &     &      &    &\ $\}$\cr
  321. \+  &      &     &      &\ $\}$ /$*$ forall\_adj\_edges $*$/\cr
  322. \+  &      &\ $\}$ /$*$ while $*$/\cr
  323. \+  &{\bf return} true;\cr
  324. \+\ $\}$\cr
  325. \vfill\eject
  326.  
  327. {\bf All Pairs Shortest Paths}
  328.  
  329. \#include \<LEDA/graph.h\>
  330. \medskip
  331. \cleartabs
  332. \+void all\_pairs\_shortest\_paths(graph\& $G$, &edge\_array\<double\>\& $cost$,\cr
  333. \+                                              &node\_matrix\<double\>\& $DIST$)\cr
  334. \cleartabs 
  335. \+$\{$\ &\cr
  336. \+      &// computes for every node pair $(v,w)$ $DIST(v,w)$ = cost of the least cost\cr
  337. \+      &// path from $v$ to $w$, the single source shortest paths algorithms BELLMAN\_FORD\cr
  338. \+      &// and DIJKSTRA are used as subroutines\cr
  339. \smallskip
  340. \+      &edge $e$;\cr
  341. \+      &node $v$;\cr
  342. \+      &double $C = 0$;\cr
  343. \smallskip
  344. \+      &{\bf forall\_edges}($e,G$) $C += fabs(cost[e]$);\cr
  345. \+      &node $s = G$.new\_node(); \hskip 3truecm         & // add $s$ to $G$\cr
  346. \+      &{\bf forall\_nodes}($v,G$) $G$.new\_edge($s,v$); & // add edges ($s,v$) to $G$\cr
  347. \smallskip
  348. \+      &node\_array\<double\> $dist1(G)$;\cr
  349. \+      &node\_array\<edge\>   $pred(G)$;\cr
  350. \+      &edge\_array\<double\> $cost1(G)$;\cr
  351. \+      &{\bf forall\_edges}($e,G$) 
  352.                  $cost1[e] = (G$.source$(e)==s)$ ? $C : cost[e]$;\cr
  353. \smallskip
  354. \+      &BELLMAN\_FORD($G,s,cost1,dist1,pred$);\cr
  355. \smallskip
  356. \+      &$G$.del\_node($s$);                              & // delete $s$ from $G$\cr
  357. \+      &edge\_array(double) $cost2(G)$;\cr
  358. \+      &{\bf forall\_edges}($e,G$) $cost2[e] = dist1[G.source(e)] + cost[e] - dist1[G.target(e)]$;\cr
  359. \smallskip
  360. \+      &{\bf forall\_nodes}($v,G$)  DIJKSTRA($G,v,cost2,DIST[v],pred$);\cr
  361. \smallskip
  362. \+      &{\bf forall\_nodes}($v,G$)\cr
  363. \+      &\quad {\bf forall\_nodes}($w,G$) $DIST(v,w) = DIST(v,w) - dist1[v] + dist1[w]$;\cr
  364. \+ $\}$\cr
  365.  
  366. \vfill\eject
  367.  
  368.  
  369. {\bf Minimum Spanning Tree}
  370.  
  371.  
  372. \#include \<LEDA/graph.h\>\nl
  373. \#include \<LEDA/node\_partition.h\>
  374. \medskip
  375. \cleartabs
  376. \+void MIN\_SPANNING\_TREE(graph\& $G$, edge\_array\<double\>\& $cost$, list\<edge\>\& $EL$)\cr
  377. \+$\{$\ \ &\cr 
  378. \+       &node $v,w$;\cr
  379. \+       &edge $e$;\cr
  380. \+       &node\_partition $Q(G)$;\cr
  381. \smallskip
  382. \+       &$G$.sort\_edges($cost$);\cr
  383. \smallskip
  384. \+       &$EL$.clear();\cr
  385. \+       &{\bf forall}\_edges($e,G$)\cr
  386. \+       &\ \ \ &$\{$ &$v = G.source(e)$;\cr
  387. \+       &      &     &$w = G.target(e)$;\cr
  388. \+       &      &     &{\bf if} ($!(Q$.same\_block($v,w$))\cr
  389. \+       &      &     &\ \ &$\{$ & $Q$.union\_blocks($v,w$);\cr
  390. \+       &      &     &    &     & $EL$.append($e$);\cr
  391. \+       &      &     &    &\ $\}$\cr
  392. \+       &      &\ $\}$\cr
  393. \+\ $\}$\cr
  394.  
  395. \vfill\eject
  396.